package ch05;

/**
 * @version: 1.0
 * @Description: TODO
 * @author: zZmH
 * @date: 2020/09/30 15:09
 */

//kmp
public class KMP {

    static int[] next;
    static String p, t;

    public static void main(String[] args) {
        //主串
        t = "abababbabaababbbabaabb";
        //模式串
        p = "babaabab";
        next = new int[p.length() + 1];

    }


    //t:主串 p:模式串
    void getNext() {

        next[0] = -1;
        int i = 0;
        int j = -1;
        while (i < p.length()) {
            if (j == -1 || p.charAt(i) == p.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }

    }

    void kmp() {
        int i = 0, j = 0;
        while (i < t.length() && j < p.length()) {
            if (j == -1 || t.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == p.length()) {
            //成功匹配！
        } else {
            //失败
        }
    }


}
